  #include <cstdio>
  #include <iostream>
  #include <fstream>
  #include <cstdlib>
  #include <cstring>
  #include <cmath>
  #include <list>

  #include "gelimits.h"
  
  using namespace std;


  #define NULL_STRING (char *) NULL
  /* Rappresenta il valore nullo per i puntatori alle stringhe di ca-
     ratteri.
  */
  #define COMMENT_CHAR '*'
  /* E' il carattere con il quale devono iniziare le righe di commen-
     nei file che contengono i dati.
  */
  #define PROB_CHAR '%'
  /* E' il carattere con il quale devono iniziare le righe che con-
     tengono le probabilit� di una regola.
  */

  #define DEFAULT_GRAMMAR_FILE "grammar.txt"
  /* E' il nome del file di default che viene letto per estrarre i sim-
   boli e le regole della grammatica.
  */
  #define MAX_CHAR_LINE 1000
  /* E' il massimo numero di caratteri che possono essere contenuti
     in una regola.
  */
  # define MAX_RULES 30
  /* E' il massimo numero di regole consentito per la grammatica.
  */
  #define MAX_CHUNKS 10
  /* E' il massimo numero di parti destre che puo' essere contenuto
     in una regola.
  */
  #define MAX_CHAR_CHUNK 30
  /* E' il massimo numero di caratteri consentito in un chunk.
  */
  #define MAX_CHAR_FILE_NAME 30
  /* E' il massimo numero di caratteri che pu� contenere il nome
     di un file che contiene dei dati da leggere. */
  #define N_ASCII_CHARS 256
   /* E' il numero di caratteri codificato in ASCII.
   */


  /*
  +++++++++++++++++ struct dict_elem +++++++++++++++++++++++++++++++++++++
  *** Definita il: 
  E' la struttura usata dalla classe Grammar per implementare un
     dizionario che associ ad ogni simbolo non terminale la relativa
     regola.
  *** Ultima modifica: ore 17.00 del 04/04/03
  */
  class Rule;
  struct dict_elem {
         char symbol;
         Rule *ptr;
  };
  /*
  +++++++++++++++++ struct chunk ++++++++++++++++++++++++++++++++++++
  *** Definita il: 
  Questa struttura � utilzzata per specificare tutti le propriet�
     di una parte sinistra di una regola:
     string:  specifica la stringa di caratteri contenuta;
     N_chars: il numero di caratteri contenuto in string;
     prob: la probabilit� associata a quella parte di essere scelta;
     terminal: indica se quella parte conrtiene solo simboli terminali;
  *** Ultima modifica: ore 17.00 del 04/04/03
  */


  struct chunk {
         char string[MAX_CHAR_CHUNK];
         int N_chars;
         double prob;
         bool terminal;
  };
  /* Questa struttura � utilzzata per specificare tutti le propriet�
     di una parte sinistra di una regola:
     string:  specifica la stringa di caratteri contenuta;
     N_chars: il numero di caratteri contenuto in string;
     prob: la probabilit� associata a quella parte di essere scelta;
     terminal: indica se quella parte conrtiene solo simboli terminali;
  */



  /******************************************************************

            Definizione delle classi: RULE e GRAMMAR.

  ******************************************************************/


  /*
  +++++++++++++++++++++++++++ classe RULE +++++++++++++++++++++++++++++
  *** Definita il: 
  Ogni oggetto di questa classe rappresenta una regola della grammatica.
  Gli oggetti di questa stringa contengono tutti le parti (chuanks) di
  una regola, sia il simbolo sinistro che tutte le parti che si trovano
  a destra. La scelta della parte da passare a seguito di una richiesta
  da parte degli oggetti della classe Grammar avviene in maniera casuale
  ma applicando comunque una distribuzione che favorisce quelle parti di
  regola che contengono solo simboli terminali. Per evitare una crescita
  incontrollata degli alberi di generazione.
  *** Ultima modifica: ore 17.00 del 04/04/03
  */
  class Rule
  {
  public:
     Rule(char *string);
     /* E' la procedura costruttrice della classe che leggendo la
        stringa in input costruisce un array di strutture chunk (defi-
        nito in grammar.h) e che rappresenta l'insieme delle parti
        destre della regola.
     */
     int give_chunk (int &N, char *string);
     /* Questa procedura memorizza nel parametro string la stringa
        che rappresenta una delle parti destre della regola. Facendo
        una scelta casuale che tiene conto delle diverse probabilit�
        memorizzate nei vari chunks. Inoltre, la procedura restitui-
        sce anche il numero di caratteri da cui � formato il chunk,
        memorizzandolo nel parametro di input N. Infine, essa resti-
	tuiisce come valore il numero del chunk scelto.
     */
     int give_chunk (int &N, char *string, int not_choose);
     /* E' la stessa definita al punto precedente. La sola differenza
        consiste nel fatto che questa procedura ha un parametro in 
        pi� (not_choose) il quale specifica quale chunk NON bisogna 
        scegliere tra quelli della regola. Serve per l'implementazi-
        dell'operatore Mutation.
     */
     void get_rule_probs(char *line);
     /* Questa procedura legge dalla stringa passata come parametro le
        probabilit� della regola, presente nel file che contiene la 
        grammatica, immediatamente sotto la riga che specifica la re-
	gola. 
     */
  private:
     int N_chunks;
     /* E' il numero di parti destre posseduto dalla regola.
     */
     char left_symbol;
     /* E' il simbolo che si trova nella parte sinistra della regola.
     */
     char rule_string[MAX_CHAR_LINE];
     /* Questa  stringa contiene tutta la regola.
     */
     bool auto_prob;
     /* Questa variabile indica se la probabilit� deve essere calco-
        lata in maniera automatica o letta dal file che contiene la 
	grammatica. 
     */
     int string_ptr;
     /* Questo numero indica il prossimo carattere da leggere nella
        stringa string_rule.
     */
     chunk chunks[MAX_CHUNKS];
     /* E' l'array che contiene tutte le parti destre della regola.
     */
     int term_chunks;
     /* Rappresenta il numero di parti destre della regola che conten-
        gono solo simboli terminali.
     */
     int not_term_chunks;
     /* Rappresenta il numero di parti destre della regola che con-
        tengono almeno un simbolo non terminale.
     */
     int get_chunk();
     /* Questa procedura leggendo la stringa rule_string, estrae un
        chunk.
     */
     void comp_probs();
     /* Questa procedura calcola le percentuali di scelta delle varie
        parti destre presenti nella regola, tenendo conto della pre-
	senza dei simboli terminali e non terminali.
     */
     void check_chunks();
     /* Questa procedura esamina i chunks della regola e calcola il
        il numero di chunks terminali (contengono solo simboli termi-
        nali) e quello dei chunks non terminali (contengono almeno un
        non terminale).
     */
     void ini_string();
     /* Inizializza la stringa rule_string e la variabile
        string_ptr. */
     void ini_chunks();
     /* Inizializza l'array di strutture chunks. */

  };
  


  /*
  +++++++++++++++++++++++++++ classe GRAMMAR +++++++++++++++++++++++++++++
  *** Definita il: 
  Ogni oggetto di questa classe rappresenta una grammatica. Gli oggetti di
  questa classe contengono un array di puntatori agli oggetti rule i quali
  contengono le singole regole della grammatica. Le regole e i simboli del-
  la grammatica vengono generati leggendo un file default oppure dando il
  nome del file come parametro alla linea di comando.
  *** Ultima modifica: ore 17.00 del 04/04/03

  */
  class Grammar
  {
  public:
     Grammar();
     /* E' la procedura costruttrice della classe. Inizia leggendo il
        file che contiene la grammatica e genera un numero di oggetti
        rule pari al numero di regole presenti nella grammatica e de-
        termina il nuemera di regole della grammatica e lo assegna come
        valore all'attributo N_rules;
     */
     int give_string (char ch, int &N, char *string);
     /* Questa procedura viene utilizzata per generare gli individui
        secondo le regole della grammatica. Essa prende come input
        (ch) un simbolo della grammatica non terminale e memorizza
        nel parametro string una delle stringhe che si trova alla
        destra della corrispondente regola, scegliendola in maniera
        casuale. Inoltre, la stringa restituisce nel parametro N il
        numero di caratteri di cui � composta la stringa restituita.
	Infine, essa restituisce il numero della clausola reativa al-
	la stringa restituita.
     */
     int give_string (char ch, int &N, char *string, int not_choose);
     /* E'la stessa procedura definita sopra. L'unica differenza � 
        che accetta un parametro in pi�, il quale specifica quale 
        clausola NON bisogna sceglier etra quelle della regola rela-
        tiva al simbolo ch. Essa serve per l'implementazione del ope-
        ratore Mutation.
       */
     char start_symbol();
     /* Restituisce il simbolo di start della grammatica. Ricordiamo
        che la regola di start DEVE essere passata per prima.
     */
     bool symbol(char ch);
     /* Verifica se il carattere in input e' un simbolo della gramma-
        tica.*/
     bool terminal(char ch);
     /* Verifica se il carattere passato come parametro � un simbolo
        terminale della grammatica.
     */
     bool not_terminal(char ch);
     /* Verifica se il carattere passato come parametro � un simbolo
        non terminale della grammatica.
     */
     void get_grammar(int argc, char *argv[]);
     /* Legge da file, di default o da quello specificato alla riga
        di comando, la grammatica da utilizzare per la generazione
        degli individui. Per ogni regola istanzia un oggetto della
        classe Rule. I parametri passati specificano la riga di comando
        per verificare quale file aprire. 
     */
     void give_grammar(ofstream *out_stream);
     /* Copia nel file passato come parametro la grammatica.
     */
     double term_probs;
     /* E' la probabilit� di scelta totale delle parti destre che
        contengono solo simboli terminali. E' uguale per tutte le
        regole della grammatica.
     */
     double not_term_probs;
     /* E' la probabilit� di scelta totale delle parti destre che
        contengono almeno un simbolo non terminale. E' uguale per
        tutte le regole della grammatica.
     */
  private:
     int N_rules;
     /* E' il numero di regole contenute nella grammatica.
     */
     dict_elem symbols_dict[MAX_RULES];
     /* Quest'array e' un dizionario che associa i simmboli non termi-
        nali delle regole agli oggetti istanziati della classe Rule
        che rappresentano le regole della grammatica. Infatti, rule �
        una struct definita in grammar.h che associa simboli non ter-
        minali a puntatori a oggetti della classe Rule.
     */
     bool terminals[N_ASCII_CHARS];
     /* Questa struttura dati serve a memorizzare i simboli terminali.
        Questa struttura dati sfrutta il fatto che il linguaggio C me-
        morizza i char sotto forma di interi. Quindi, un char pu� an-
        che indirizzare l'array.
        Es. se il carattere 'a' fa parte  dei terminali terminals['a']
        vale True in caso contrario vale false
     */
     bool not_terminals[N_ASCII_CHARS];
     /* Questa struttura dati serve a memorizzare i simboli non termi-
        nali presenti nella grammatica. E sfrutta lo stesso principio
        illustrato al punto precedente.
     */
     char file_name[MAX_CHAR_FILE_NAME];
     /* E' il nome del file che contiene la grammatica.
     */
     FILE *file_ptr;
     /* E' il puntatore al file che contiene la grammatica.
     */
     char get_first_symbol();
     /* E' una procedura di utilit� ed chiamata da get_rule e serve a
        saltare i commenti e i caratteri bianchi e di newline presenti
        nel file che contiene la grammatica.
     */
     void get_symbols();
     /* Questa procedura serve a leggere dal file della grammatica sia
        la lista dei siumboli terminali che dei non terminali.
     */
     void get_terminals(char *string);
     /* Questa procedura viene chiamata da get_symbols e legge dalla
        stringa in iput lista dei simboli terminali.
     */
     void get_not_terminals(char *string);
     /* Questa procedura viene chiamata da get_symbols e legge dalla
        stringa in input la lista dei simboli non terminali.
     */
     void get_def_probs();
     /* Questa procedura estrae dal file della grammatica le probabi-
        lita' di default per la scelta delle clausole  terminali (con-
        tenenti solo simboli termianli) e non terminali (contenenti
        almeno un simbolo non terminale). 
     */
     bool extract_probs(char *line);
     /*	Estrae dalla linea in input il valore di probabilit� contenu-
      	to e lo assegna alla relativa variabile.
     */	
     void ini_symbols();
     /* Inizializza le strutture dati che contengono le liste dei
        terminali e dei non terminali.
     */
  };

